// Longest subsequence containing equal number of 0's and 1's

#include <iostream>
using namespace std;
/*This is the given array from which we have to find the subarray with equal no of 0 and 1*/
int a[] = {1,1,0,1,0,0,0,1,1,0,0,1,1,1,0,0,0,0,1,1,1,0,1};
int k = sizeof(a)/sizeof(int) - 1;
int i = 0;
int v = 0;

/*This function determine how many 1s are exceeding 0, It can be negative*/
void value()
{
	for(int i = 0; i<=k; i++)
	{
		if(a[i])
		v++;
		else v--;
	}
}
/*This function recursively remove a element(0 or 1) which exceeds and return when v is 0*/
void longestsubsequence(int p, int q)
{
	//Base condition
	if(v==0)
	return;
	
	if(v>0)
	{
		while(p<q && v)
		{
			if(a[p])
			{
				p++;
				i=p;
				v--;
				if(v==0)
				return;
				longestsubsequence(i,k);
			}
			else if(a[q])
			{
				q--;
				k=q;
				v--;
				if(v==0)
				return;
				longestsubsequence(i,k);
			}
			else
			{
				p++;
				q--;
				v+=2;
			}
		}
	}
	if(v<0)
	{
		while(p<q && v)
		{
			if(!a[p])
			{
				p++;
				i=p;
				v++;
				if(v==0)
				return;
				longestsubsequence(i,k);
			}
			else if(!a[q])
			{
				q--;
				k=q;
				v++;
				if(v==0)
				return;
				longestsubsequence(i,k);
			}
			else
			{
				p++;
				q--;
				v-=2;
			}
		}
	}
}


int main()
{
	int m = 0;
	value();
	longestsubsequence(i,k);
	for(int l = i; l<=k; l++)
	{
		cout << a[l] << "  ";
		if(a[l]) m++;
		else m--;
	}
	cout << "\nbalance is : " << m << "\n";
	return 0;
}
